Abstract: There is growing interest in improving our algorithmic understanding of fundamental statistical problems such as mean estimation, driven by the goal of understanding the fundamental limits of what we can extract from limited and valuable data. The current state-of-the-art results for one-dimensional mean estimation are proven optimal only in the worst case, so motivated by the recent effort in the community to go 'beyond the worst-case analysis' of algorithms, we initiate the fine-grained study of the mean estimation problem in one dimension - more concretely, we ask whether we can devise algorithms that performs better than the worst-case optimal 'sub-Gaussian performance', at least for some distributions.
We answer this question in the negative, at least asymptotically. Given a distribution $p$, assuming only that it has a finite mean and absent any additional assumptions required by previous results, we show how to construct another distribution $q$ such that $p$ and $q$ are impossible to accurately distinguish, yet have well-separated means, which implies that no reasonable estimator can expect to asymptotically achieve better than the sub-Gaussian error rate, matching previous worst-case optimality results.
We furthermore introduce a new definitional framework to analyze the fine-grained optimality of algorithms, which interpolates between popular beyond worst-case optimality notions, which are inapplicable to our setting. As an application of the new framework, we show that the standard median-of-means estimator is optimal in our framework, up to constant factors.
Based on joint work with Paul Valiant (Purdue), Jasper C.H. Lee (UW Madison), and Trung Dang (UT Austin; Work done at Purdue), to appear in NeurIPS 2023.